
//class Solution {
//    static class ListNode {
//        int val;
//        ListNode next = null;
//
//        ListNode(int val) {
//            this.val = val;
//        }
//    }
//public ListNode deleteDuplication(ListNode head) {
//    /*又把简单的代码写地又臭又长*/
//    if (head == null) {
//        return null;
//    }
//    ListNode ret = new ListNode(-1);
//    ListNode repeat = new ListNode(-1);
//
//    //记录尾节点，便于尾插
//    ListNode retRear = ret;
//    ListNode repeatRear = repeat;
//
//    //先搭建框架
//
//    //遍历head链表
//    while(head != null) {
//        //检查当前节点在ret中是否存在
//        int index = check(ret,head);
//        //不存在时 再判断在重复链表中是否存在
//        if(index < 0) {
//            //当重复链表也不存在时，将该链表插入到ret
//            //若是重复链表中存在，不做操作
//            if(check(repeat,head)<0) {
//                retRear.next = head;
//                retRear = retRear.next;
//            }
//        } else {
//            //若是在ret链表中已经存在 1将其插入到重复链表 2在ret链表中将其删除
//            ListNode prev = null;
//            if(index==0) {
//                prev = ret;
//            } else {
//                prev = ret.next;
//                while(index-1 != 0){
//                    prev = prev.next;
//                    index--;
//                }
//            }
//            ListNode del = prev.next;
//            repeatRear.next = del;
//            repeatRear = repeatRear.next;
//
//            prev.next = del.next;
//        }
//        head = head.next;
//    }
//    return ret.next;
//}
//
//    public int check(ListNode recordRet,ListNode head) {
//        ListNode cur = recordRet.next;
//        for(int i = 0; cur!=null; i++) {
//            if(cur.val == head.val) {
//                return i;
//            }
//            cur = cur.next;
//        }
//        return -1;
//    }
//}
class Solution {
    static class ListNode {
        int val;
        Solution.ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 正确的解法：*/
    public ListNode deleteDuplication(ListNode head) {
        if (head == null) {
            return null;
        }
        int record = -1;
        //给这个链表加上一个头节点
        ListNode prev = new ListNode(-1);
        ListNode ret = prev;
        prev.next = head;

        ListNode cur = head;

        while(cur!=null) {
            if(cur.next!=null && cur.val == cur.next.val || cur.val == record) {
                record = cur.val;
                prev.next = cur.next;
            } else{
                prev = cur;
            }
            cur = cur.next;
        }
        return ret.next;
    }
}
